// EditDistance.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <string>
#include <vector>
#include <math.h>
using namespace std;
class Solution {
public:
    int minDistance(string word1, string word2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(word1.size()==0) return word2.size();
        if(word2.size()==0) return word1.size();
        
        vector<vector <int> > mt(word1.size(), vector<int>(word2.size(), 0));
        int nMax = 0;
        if(word1[0] == word2[0])
        {
            mt[0][0] = 1;
            nMax =1;
        }
        
        for(int i = 1; i<word1.size(); i++)
        {
            if(word1[i] == word2[0])
            {
                mt[i][0] = 1;
                nMax =1;
            }
            else
            {
                mt[i][0] = mt[i-1][0];
            }
        
        }
        
        for(int j = 1; j<word2.size(); j++)
        {
            if(word1[0]== word2[j])
            {
                mt[0][j] = 1;
                nMax = 1;
            }
            else
                mt[0][j]= mt[0][j-1];
        }
        
        for(int i = 1; i<word1.size();i++)
        {
            for(int j = 1; j<word2.size(); j++)
            {
                if(word1[i] == word2[j])
                {
                    mt[i][j] = mt[i-1][j-1]+1;
                    nMax = max(mt[i][j], nMax);
                }
                else
                {
                    mt[i][j] = mt[i][j-1];
                }
            }
        }

        int dist = abs(int(nMax -word1.size()));

        dist= max(dist, abs(int(nMax-word2.size())));
        return dist;
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
	Solution S;
	S.minDistance("park", "spake");
	return 0;
}

